#include "tools.cpp"
// leetcode 32

class Solution_simple {
  public:
    int longestValidParentheses(std::string s) {
        int resutl = 0;
        point_longest(s, resutl, 0);
        return resutl;
    }

    int point_longest(const std::string& s, int& cur_max, int start) {
        if (start > s.size()) return 0;
        int tmp = start;
        int left = 0;
        int result = 0;
        for (; start < s.size(); ++start) {
            if (s[start] == '(') {
                ++left;
            } else {
                if (left == 0) break;
                result += 2;
                --left;
                if (left == 0) {
                    result += point_longest(s, cur_max, start + 1);
                    cur_max = std::max(cur_max, result);
                    return result;
                }
            }
        }
        point_longest(s, cur_max, tmp + 1);

        return 0;
    }
};

class Solution {
  public:
    int longestValidParentheses(std::string s) {
        if (s.empty()) return 0;
        int result = 0;
        dp = std::vector<int>(0, s.size());
        longestValidParentheses(s, 0, result);
        print(dp);
        return result;
    }

    // we need right board and result
    std::pair<int, int> longestValidParentheses(std::string& s, int start, int& result) {
        if (start >= s.size()) return make_pair(s.size() + 3, s.size() + 3);
        if (dp[start] != 0) return make_pair(start, start + dp[start] - 1);
        int high = s.size() + 3, low = s.size() + 3;

        std::cout << start << std::endl;
        for (int i = start; i < s.size() - 1; ++i) {
            if (is_parenthese(s[i], s[i + 1])) {
                high = i + 1, low = i;
                while (true) {
                    if (low >= 1 and high < s.size() - 1 and is_parenthese(s[low - 1], s[high + 1])) {
                        ++high, --low;
                    } else if (auto tmp = longestValidParentheses(s, high + 1, result); tmp.first == high + 1) {
                        high = tmp.second;
                    } else {
                        break;
                    }
                }
                dp[start] = high - low + 1;
                result = std::max(result, dp[start]);
                break;
            }
        }
        return std::make_pair(low, high);
    }

  private:
    std::vector<int> dp;
    bool is_parenthese(char left, char right) { return left == '(' and right == ')'; }
};

int main() {
    std::string str{")()())()()("};
    Solution s;
    std::cout << s.longestValidParentheses(str) << std::endl;
}
